1. Field of the Invention
This invention generally relates to the field of microprocessors, and more particularly to a circuit and method for dividing a signed numerator by a signed denominator and for determining whether the division results in an overflow condition.
2. Description of the Relevant Art
Microprocessors determine the speed and power of personal computers, and a growing number of more powerful machines, by handling most of the data processing in the machine. Microprocessors typically include at least three functional groups: the input/output unit (I/O), the control unit, and the arithmetic logic unit (ALU). The I/O unit interfaces between external circuitry and the ALU and the control unit. I/O units frequently include signal buffers for increasing the current capacity of a signal before the signal is sent to external components. A control unit controls the operation of the microprocessor by fetching instructions from the I/O unit and translating the instructions into a form that can be understood by the ALU. In addition, the control unit keeps track of which step of the program is being executed. The ALU handles the mathematical computations and logical operations that are performed by the microprocessor. The ALU executes the decoded instructions received from the control unit in order to modify data contained in registers within the microprocessor.
One essential function of the ALU is to execute instructions for dividing operands. The ALU typically performs division on at least two input operands, a numerator and a denominator. In general, dividing the numerator by the denominator results in a quotient and a remainder. In other words: EQU N=QD+R (1)
where N represents the numerator, Q represents the quotient, D represents the denominator, and R represents the remainder. N, the first operand, can be represented by up to 2n-bits. D, the second operand, can be represented by up to n-bits. With N represented by up to 2n-bits and D represented by up to n-bits, Q and R can generally represented by up to n-bits.
Often times, the division of the two operands, N and D, will result in an overflow condition. Generally, with respect to signed operands, an overflow condition occurs when Q and/or R do not fit within the following ranges: EQU -2.sup.n-1 .ltoreq.Q.ltoreq.2.sup.n-1, or (2) EQU -.vertline.D.vertline.+1.ltoreq.R.ltoreq..vertline.D.vertline.-1.(3)
It is important to detect the occurrence of an overflow condition when dividing two signed operands. Typically a flag is set within the microprocessor when an overflow condition results from the division of two signed operands. The flag, once set, alerts the software to jump to, for example, an exception routine. The exception routine, in turn, alerts the system of the overflow or error encountered. In .times.86 architectures, when a division overflow condition arises, an interrupt routine is immediately called which interrupts the application.
One of ordinary skill in the art will recognize that an overflow condition will not occur if the following equations hold true: EQU Q=-2.sup.n-1 or .vertline.Q.vertline..ltoreq.2.sup.n-1 -1, and(4) EQU .vertline.R.vertline..ltoreq..vertline.D.vertline.-1. (5)
Equation 5 follows from the observation that the remainder must always be less than the denominator. Ignoring the situation in which Q equals the maximum negative allowable value (i.e., -2.sup.n-1), one of ordinary skill in the art will recognize from the above equations that an overflow condition will not occur in a signed division operation if: EQU .vertline.N.vertline..ltoreq.(2.sup.n-1).vertline.D.vertline.-1(6)
Equation 6 reduces to the following: EQU .vertline.N.vertline.&lt;2.sup.n-1 .vertline.D.vertline. (7)
Equation 7 is implemented in the prior art to determine whether an overflow condition occurs when dividing two signed operands N and D. The prior art implementation has severe disadvantages. The prior art implementation requires (1) checking the numerator and the denominator to determine whether they are negative values, (2) calculating absolute values for the denominator and the numerator if they are negative, (3) shifting the absolute value of the denominator (which is the same as multiplying the denominator by 2.sup.n-1), and (4) comparing the absolute value of the numerator against the shifted absolute value of the denominator. Each of these four steps requires significant processing time and hardware. For example, the absolute value calculations may involve two's complement operations. The time needed to perform a two's complement operation on an operand depends upon the length of the operand. In a 32-bit microprocessor, N could be up to 64 bits wide while D could be up to 32 bits wide. Performing a two's complement on 64-bit and 32-bit operands can require significant processing time. Further, implementing Equation 7 to detect an overflow condition requires a 64-bit comparison between the absolute value of N and the absolute value of D shifted left 32 bits with zero fill.
A faster method is needed for determining whether an overflow condition arises during signed operand division which avoids testing the numerator and denominator to determine whether they are negative operands, inverting the numerator and denominator when they are negative, multiplying the denominator by 2.sup.n-1 and comparing 2n-bit wide operands to determine which is larger.